package com.LeeCode;


/**
 * 将数组分成三个子数组的方案数
 */

public class Code1712 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 2, 5, 0};
        System.out.println(new Code1712().waysToSplit(nums));
    }

    public int waysToSplit(int[] nums) {
        int MOD = 1_000_000_007;
        int n = nums.length;
        int[] prefixSum = new int[n + 1];

        // 构建前缀和数组
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int count = 0;

        // 固定 i，滑动 j
        for (int i = 1; i < n - 1; i++) {
            // 使用二分法找到满足条件的最小 j
            int low = i + 1;
            int high = n - 1;
            int left = prefixSum[i];
            int minMid = left;
            int maxMid = (prefixSum[n] + left) / 2;

            // 找到第一个满足 prefixSum[j] >= 2 * left 的 j
            int start = -1;
            int l = i + 1, r = n - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (prefixSum[mid] >= 2 * left) {
                    start = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            if (start == -1) continue;

            // 找到最后一个满足 prefixSum[j] <= (prefixSum[n] + left) / 2 的 j
            int end = -1;
            l = start;
            r = n - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (prefixSum[mid] <= (prefixSum[n] + left) / 2) {
                    end = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            if (end != -1 && end >= start) {
                count = (count + end - start + 1) % MOD;
            }
        }

        return count;
    }
}
